package sort.leetcode;

/**
 * 剑指 Offer 51. 数组中的逆序对
 * @author haomin
 * @date 2022/03/19 17:56
 **/
public class NumOffer51_reversePairs {
    public int reversePairs(int[] nums) {
        return reversePairsHelper(nums,0,nums.length - 1);
    }

    private int reversePairsHelper(int[] nums, int l, int r) {
        if(l - r >= 0){
            return 0;
        }

        int mid = l + ((r - l) >> 1);
        int left = reversePairsHelper(nums,l,mid);
        int right = reversePairsHelper(nums,mid + 1,r);

        if(nums[mid] > nums[mid + 1]){
            return mergeSort(nums,l,mid,r) + left + right;
        }else {
            return left + right;
        }
    }

    private int mergeSort(int[] nums, int l, int mid, int r) {
        int[] aux = new int[r - l +1];
        for (int i = 0; i < aux.length; i++) {
            aux[i] = nums[i + l];
        }

        int ret = 0;
        int i = l;
        int j = mid +1;
        for (int k = l; k <= r; k++) {
            if(i > mid){
                nums[k] = aux[j - l];
                j++;
            }else if(j > r){
                nums[k] = aux[i - l];
                i++;
            }else if(aux[i - l] <= aux[j - l]){
                nums[k] = aux[i - l];
                i++;
            }else {
                ret += (mid - i) + 1;
                nums[k] = aux[j - l];
                j++;

            }
        }
        return ret;
    }
}